#ifndef _LINEARLIST_H
#define _LINEARLIST_H

#include "common\cxMacros.h"
/*
*array:location(i) = location(i-1).
*
* location(i) = (location(1)+i -1)% maxSize.
*/
template<typename T>
class LinearList
{
	T* m_data;
	int m_maxSize;
	int m_first;
	int m_last;
public:

	LinearList();
	~LinearList();

	bool isEmpty() {
		return (m_last- m_first!=0)&& m_first != -1 ?false:true;
	}
	int size(){
		return (m_last - m_first >= 0)&&m_first!=-1 ? (m_last - m_first+1):0;
	}

	bool find_ll(int k,T& value);
	int search_ll(const T& value);
	int delete_ll(int k,T& value);
	int insert_ll(const T& value,int k = 0); 
private:
	// loction. k ( 0....n).
	int _loctionInArray(int k){
		return (m_first + k)%m_maxSize;
	}
	int _loctionInterface(int loction){
		return ( loction - m_first)%m_maxSize;
	}
	T& _find(int k,int& loction){

	}
};

template<typename T>
LinearList<T>::LinearList():
m_first(-1),m_last(-1),m_maxSize(1)
{
	m_data = new T[m_maxSize];
}

template<typename T>
LinearList<T>::~LinearList()
{
	CX_SAFE_DELETE_ARRAY(m_data);
}

template<typename T>
bool LinearList<T>::find_ll(int k,T& value)
{
	if(isEmpty()){
		return false;
	}
	value = m_data[_loctionInArray(k)];
	return true;
}

template<typename T>
int LinearList<T>::search_ll(const T& value)
{
	int index = -1;
	if (isEmpty())
	{
		return index;
	}
	index = m_first;
	for(; index <= m_last; i++)
	{
		if(m_data[index] == value){
			break;
		}
	}
	return _loctionInterface(index);
}

template<typename T>
int LinearList<T>::delete_ll(int k,T& value)
{
	int index = -1;
	if(isEmpty()){
		return index;
	}
	if(find_ll(k,value)){
		return index;
	}
	index = _loctionInArray(k);
	if( index - m_first > m_last - index	){
		for( int i = index ; i < m_last ; ++i){
			m_data[i] = m_data[i+1];
		}
		m_last --;
	}else{
		for( int i = index ; i > m_first ; --i){
			m_data[i] = m_data[i-1];
		}
		m_first++;
	}
}

template<typename T>
int LinearList<T>::insert_ll(const T& value,int k /* = 0 */)
{
	int index = -1;
	if(isEmpty()||search_ll(value)!=-1){
		return index;
	}
}
#endif